package main

import "fmt"

// 如何求解字符串中字典序最大的子序列

func main() {
	s := "acbdxmng"
	fmt.Println(getLargestSub(s))

	s = "acbdxmng"
	fmt.Println(getLargestSub2(s))
}

// 逆序遍历法
func getLargestSub2(txt string) string {
	ll := len(txt)
	largestSub := make([]byte, ll+1)

	// 最后一个字符一定在子串中
	largestSub[0] = txt[ll-1]
	i := ll - 2
	j := 0

	// 逆序遍历字符串
	for ; i >= 0; i-- {
		if txt[i] >= largestSub[j] {
			j++
			largestSub[j] = txt[i]
		}
	}
	largestSub[j+1] = ' '

	// 对子串进行逆序遍历
	for i = 0; i < j; i, j = i+1, j-1 {
		largestSub[i], largestSub[j] = largestSub[j], largestSub[i]
	}

	return string(largestSub)
}

// 顺序遍历法
func getLargestSub(str string) string {
	ll := len(str)
	largestSub := make([]byte, ll+1)
	k := 0
	for i := 0; i < ll; i++ {
		largestSub[k] = str[i]
		for j := i + 1; j < ll; j++ {
			/// 找出第 i 个字符后面最大的字符放到 largestSub[k] 中
			if str[j] > largestSub[k] {
				largestSub[k] = str[j]
				i = j
			}
		}
		k++
	}
	return string(largestSub[0:k])
}
